#include<stdio.h>
#include<string.h>
struct data {
	char value[100000];
	int k;
};

void buildNext(char *P, int next[], int m){ int k=next[0]=-1;
for(int j=0; j<m; j++){ 
while(k>=0 && P[k]!=P[j])
k=next[k];
next[j+1]=++k;
}
}

const int N=1e4+10;
void KMP(char S[], char P[], int n, int m){
 int next[N],i=0,j=0,cnt=0; 
 buildNext(P, next, m); 
  while(j<m && i<n) { if(j==-1 || S[i]==P[j]) i++, j++;
else j=next[j];
if (j == m) { 
cnt++; 
j=next[j];}}
printf("%d\n",cnt);
}


struct data op[9];
int main() {
	int t;
	scanf("%d", &t);
	int a;
	for (a = 0; a < t; a++) {
		scanf("%s", &op[a].value);
		scanf("%d", &op[a].k);
	}
	char p[100000];
	for (a = 0; a < t; a++) {
		int m=-1;
		while (m < (op[a].k - 1) * 5) { p[++m] = 'e'; p[++m] = 'd'; p[++m] = 'g'; p[++m] = 'n'; p[++m] = 'b'; }
		
		int n = strlen(op[a].value);
		KMP(op[a].value,p,n,m);
		
	}
	


	return 0;
}